package pers.qianyu.month_202012.date_20201223;

import org.junit.*;

import java.util.*;

/**
 * 130. 被围绕的区域
 * https://leetcode-cn.com/problems/surrounded-regions/
 *
 * @author mizzle rain
 * @date 2020-12-23 15:04
 */
public class SurroundedRegions2 {
    // 使用并查集
    public void solve(char[][] board) {
        int h = board.length;
        if (h == 0) {
            return;
        }
        int w = board[0].length;
        if (w == 0) {
            return;
        }
        int key = w * h;
        UF uf = new UF(key + 1);
        for (int i = 0; i < h; i++) {
            if (board[i][0] == 'O') {
                uf.union(key, i * w);
            }
            if (board[i][w - 1] == 'O') {
                uf.union(key, i * w + w - 1);
            }
        }
        for (int i = 0; i < w; i++) {
            if (board[0][i] == 'O') {
                uf.union(key, i);
            }
            if (board[h - 1][i] == 'O') {
                uf.union(key, w * (h - 1) + i);
            }
        }
        int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 1; i < h - 1; i++) {
            for (int j = 1; j < w - 1; j++) {
                if (board[i][j] == 'O') {
                    for (int[] dri : direction) {
                        int x = i + dri[0];
                        int y = j + dri[1];
                        if (board[x][y] == 'O') {
                            uf.union(i * w + j, x * w + y);
                        }
                    }
                }
            }
        }
        System.out.println(Arrays.toString(uf.parent));
        for (int i = 1; i < h - 1; i++) {
            for (int j = 1; j < w - 1; j++) {
                if (board[i][j] == 'O' && !uf.connected(key, i * w + j)) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    /**
     * 并查集内部类
     *
     * @author mizzle rain
     * @date 2020年12月23日16:00:05
     */
    private static class UF {
        private int count;
        private int[] size;
        private int[] parent;

        public UF(int count) {
            this.count = count;
            this.size = new int[count];
            this.parent = new int[count];
            for (int i = 0; i < count; i++) {
                this.parent[i] = i;
                this.size[i] = 1;
            }
        }

        public void union(int p, int q) {
            int rootP = findRoot(p);
            int rootQ = findRoot(q);
            if (rootP == rootQ) {
                return;
            }
            if (size[rootP] > size[rootQ]) {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            } else {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            }
            count--;
        }

        public boolean connected(int p, int q) {
            return findRoot(q) == findRoot(p);
        }

        private int findRoot(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        public int count() {
            return count;
        }
    }

    @Test
    public void test1() {
        char[][] arr = {
                {'O', 'O'},
                {'O', 'O'},
        };
        new SurroundedRegions2().solve(arr);
        Arrays.stream(arr).forEach(i -> System.out.println(Arrays.toString(i)));
    }

    @Test
    public void test2() {
        char[][] arr = {
                {'O', 'O', 'O'},
                {'O', 'O', 'O'},
                {'O', 'O', 'O'},
        };
        new SurroundedRegions2().solve(arr);
        Arrays.stream(arr).forEach(i -> System.out.println(Arrays.toString(i)));
    }

    @Test
    public void test3() {
        char[][] arr = {
                {'X', 'X', 'X', 'X'},
                {'X', 'O', 'O', 'X'},
                {'X', 'X', 'O', 'X'},
                {'X', 'O', 'X', 'X'},
        };
        new SurroundedRegions2().solve(arr);
        Arrays.stream(arr).forEach(i -> System.out.println(Arrays.toString(i)));
    }

    @Test
    public void test4() {
        char[][] arr = {
                {'O', 'X', 'X', 'O', 'X'},
                {'X', 'O', 'O', 'X', 'O'},
                {'X', 'O', 'X', 'O', 'X'},
                {'O', 'X', 'O', 'O', 'O'},
                {'X', 'X', 'O', 'X', 'O'}
        };
        new SurroundedRegions2().solve(arr);
        Arrays.stream(arr).forEach(i -> System.out.println(Arrays.toString(i)));
    }
}
